暑期班汇总
2025暑期班
把所有的内容全部汇总到同一篇文章中,便于查找。
2025年6月30日 扫描线与Arrangement
输入输出
输入:
1 | 一组 x‑单调曲线(X_monotone_curve_2)和/或点(Point_2),它们位于一个二维参数域(如平面或曲面)上 。 |
输出:
1 | 一个 二维细分(arrangement),即由这些曲线/点引起的细胞划分,包括顶点、边(由曲线段表示)和面,整体储存在一个 DCEL(双连通边列表)数据结构中 。 |
其解决了什么问题
这个模块解决了在平面或曲面上由多条(可能相交的)x‑单调曲线构建精确细分的问题,支持:
增量插入:可以逐条插入曲线(insert / insert_non_intersecting_curve),自动处理交点、重叠、拆分等 。
处理交叉与重叠:需要模型 ArrangementXMonotoneTraits_2,支持交点计算、曲线分解与合并 。
输入输出格式化:支持读写 arrangement 至/自流(ArrangementInputFormatter / OutputFormatter) 。
广泛应用于计算几何——如构建 Voronoi 图、布尔运算、Minkowski 和球面几何等 。
2025年7月1日 微分几何-曲线
曲线的切向量
1 | 对一条参数曲线: |
其几何意义为:表示点沿着曲线运动时的瞬时方向
单位切向量与弧长参数化
单位切向量定义为切向量的单位化形式:
$$
T(t)=\gamma^{\prime}(t)=\left(\frac{dx}{dt},\frac{dy}{dt}\right)\quad\text{或}\quad\left(\frac{dx}{dt},\frac{dy}{dt},\frac{dz}{dt}\right)
$$
而弧长参数化是指重新用”沿曲线的真实长度s”作为参数的曲线表示形式,其满足:
$$
|| \frac{d\gamma}{ds}|| = 1
$$
即在任意s处,单位切向量恒为单位长度。
曲率
曲率描述的是曲线在某点弯曲的成都,直觉上即为”拐的有多厉害”。
对于平面曲线,曲率定义为单位切向量关于弧长的变化率:
$\kappa(s)=\left|\frac{d\hat{T}}{ds}\right|$对于任意参数t,则有:
$\kappa(t)=\frac{|\gamma^{\prime}(t)\times\gamma^{\prime\prime}(t)|}{|\gamma^{\prime}(t)|^3}\quad\mathrm{(3D)},\quad\kappa(t)=\frac{|x^{\prime}y^{\prime\prime}-y^{\prime}x^{\prime\prime}|}{(x^{\prime\prime}2+y^{\prime\prime}2)^{3/2}}\quad\mathrm{(2D)}$
直线:$k = 0$
圆:$k = 1/R$
法向量与曲率向量
法向量$N(t)$ : 垂直于单位切向量的方向,指向曲线”弯曲的那一侧”。
曲率向量$k(t)$ : 曲率与法向量的乘积
$$
\vec{k}(t) = k(t) · N(t)
$$
几何意义:
法向量给出了”朝内”的方向
曲率法向量综合表达了弯曲程度+弯曲方向
2025年7月2日 微分几何-曲面
曲面的表示方法
1:参数化形式
$$
X(u,v) = (x(u,v),y(u,v),z(u,v))
$$
- 支持从二维区域映射到三维空间
2:隐式表示
$$
f(x,y,z) = 0
$$
- 用于重建、隐函数建模(SDF)
3:显式表示
$$
z=f(x,y)
$$
- 表达能力弱,仅可用于特定局部场景
混合积 (Mixed Product)
给定三个三维向量$a,b,c$,它们的混合积定义为:
$$
[a,b,c] = a·(b×c)
$$
几何意义:
1 | 混合积表示的是由三维向量a,b,c构成的平行六面体的有向体积 |
- 若混合积>0:右手系,体积为正
- 若混合积<0:左手系,体积为负
- 若混合积=0:三向量共面,体积为0
无向体积:$V = |[a,b,c]|$
使用场景:判断三向量是否共面
共变导数 (Covariant Derivative)
为了解决一个根本问题:
1 | 在弯曲空间或曲面上,怎么“正确地”比较两个不同点处的向量? |
基本定义
设 $M$ 是一个曲面或流形,$\vec{X}$ 是一个向量场,$\vec{V} \in T_pM$ 是某点处的切向量,则:
$\nabla_{\vec{V}}\vec{X}$
表示:在方向 $\vec{V}$ 上,向量场 $\vec{X}$ 的变化率,结果仍在切空间 $T_pM$ 内部。
它是一种“修正过的导数”,避免了将向量导出曲面的错误。
计算过程
令 $x^1, x^2, \dots, x^n$ 是局部坐标系
设向量场:
$$
\vec{X} = X^i \frac{\partial}{\partial x^i}
$$
共变导数公式:
$$
\nabla_j X^i = \frac{\partial X^i}{\partial x^j} + \Gamma^i_{jk} X^k
$$
其中:
$\Gamma^i_{jk}$ 是 Christoffel 符号(联络系数),反映了坐标轴自身的“弯曲”。
Christoffel 符号的计算
若给定度量 $g_{ij}$(即第一基本形式),则 Christoffel 符号通过如下公式计算:
$$
\Gamma^i_{jk} = \frac{1}{2} g^{im} \left( \frac{\partial g_{mj}}{\partial x^k} + \frac{\partial g_{mk}}{\partial x^j} - \frac{\partial g_{jk}}{\partial x^m} \right)
$$
其中 $g^{im}$ 是 $g_{ij}$ 的逆矩阵。
在测地线方程中的应用
测地线要求:
$$
\nabla_{\dot{\gamma}} \dot{\gamma} = 0
$$
也就是说,速度向量场在自身方向上的共变导数为零。
展开成坐标形式:
$$
\ddot{x}^i + \Gamma^i_{jk} \dot{x}^j \dot{x}^k = 0
\quad \text{for all } i = 1, 2, \dots, n
$$
这就是测地线方程的局部表达式。
2025年7月3日 网格曲面的基本结构-拉普拉斯算子
拉普拉斯算子
在连续情况下,拉普拉斯算子是:
$$
\Delta u = \nabla \cdot \nabla u
$$
而在网格曲面上(离散几何处理),它通常使用cotangent Laplacian表示为:
$$
\Delta u_i = \frac{1}{2A_i} \sum_{j\in N(i)}(cot\alpha_{ij}+cot\beta_{ij})(u_j-u_i)
$$
其中:
- $u_i$是顶点上的函数值,如温度、高程、颜色等
- $A_i$是顶点面积权重,如Voronoi面积或1/3面积
- $\alpha,\beta$是相邻三角形对该边的对角
拉普拉斯方程:$\Delta u = 0$
定义:无源稳态的扩散问题(调和函数)
几何 / 物理意义:
- 系统已经达到稳定状态,没有任何源项
- 函数值在局部邻域内的加权平均等于自身 -> “无弯曲方向”
- 等价于极小化函数在曲面上的Dirichlet能量
曲面网格上的应用:
- 利用$\Delta u = 0$消除高频扰动,用于Mesh Fairing / 平滑
- 利用调和映射保持角度结构,用于UV参数化
泊松方程:$\Delta u = f$
定义:有源稳态扩散项,源项$f$指定了空间中函数变化的“原因”
几何 / 物理意义:
系统稳定但内部有源项,如热源,电荷,外力等
拉普拉斯方程的推广,可用最小能量原理表示为:
$$
\underset{u}{min}\int_M||\nabla u||^2 - 2fu
$$
网格曲面上的应用:
- 利用点云->法向->源项$f$这一思路重建表面,即泊松表面重建
- 利用源图像梯度作为$f$,实现图像融合
- 基于法线散度生成泊松源项,求解SDF
无源热方程:$\frac{\partial u}{\partial t} = \Delta u$
定义:描述随时间演化的扩散过程(如热传导、污染扩散)
几何 / 物理意义:
- 初始函数$u(x,0)$经过拉普拉斯控制的平滑演化;
- 模型具有“高频信息快速衰减”的特性;
- 时间越长越趋于均匀分布。
网格曲面上的应用:
- 利用热扩散定义的点的局部特征实现Heat Kernel Signature
- 利用热扩散+归一化梯度场反推测地线估计距离
振动模态方程:$\frac{\partial^2 u}{\partial t^2} = \Delta u$
也写作$\Delta \phi = -\lambda \phi$ (特征值问题)
定义:描述物体随时间的自然振动,如鼓面、琴弦等。
几何 / 物理意义:
- 在曲面上传播的波动现象;
- 不同频率的特征函数$\phi_i$,表示不同的振动模式;
- 常用于找出“物体最自然的变形方向”。
网格曲面上的应用:
- 利用拉普拉斯特征函数变形共振模式以实现模态分析
- 利用特征值作为全局shape descriptor实现形状检索
- 利用振动模态构成模拟基础来实现物理仿真
2025年7月4日 渲染
最实用的渲染工具:blender-toolbox
感觉,没什么好说的
2025年7月5日 网格曲面的提取
M/arching Cubes(MC)
核心思想:在规则的三维体素网格上,对每个小立方体判断其八个顶点是否在等值面内,通过256种拓扑配置之一,查表生成三角面片。
优点:简单高效,适合GPU实现
缺点:可能产生拓扑不一致,难以处理尖锐边缘
Marching Tetrahedra(MT)
核心思想:将一个立方体划分为多个四面体,在每个四面体中进行线性插值并构造三角面片
优点:避免MC的拓扑不一致问题
缺点:结果比MC更细碎,可能有更多三角形
Dual Contouring(DC)
核心思想:不直接生成三角片,而是计算每个体素的等值面交点,生成“dual vertex”(一般在体素内部,通过 QEF 求解最佳点),再连接这些点生成面片。
优点:保留锐利特征(如边角),输出结构更紧凑
缺点:实现复杂,依赖高质量的梯度信息
Dual Marching Cubes(DMC)
- 核心思想:结合 MC 和 DC 的优势,构建 dual 网格但沿用 marching cubes 的遍历框架
- 优点:支持细节表达,适合处理复杂结构,拓扑更好
- 缺点:实现较复杂,算法细节多,较难调试
FlexiCubes
核心思想:一种拓扑可控的等值面提取方法,自动在规则网格中选择适当的网格单元分辨率(adaptive cells),使得重建的网格可以更好地保留特征和拓扑结构。
优点:支持高质量拓扑结构(如避免小孔或错误连接),可扩展性强
缺点:实现更复杂,需要预处理
Reach for the Spheres(RFTS)
- 核心思想:使用球体(spheres)而非体素作为构建块来提取等值面,避免了传统方法中的笛卡尔栅格偏置。使用一组球进行空间覆盖,再利用球的交叠关系推导网格。
- 优点:表面更平滑,避免体素栅格导致的锯齿状误差,更好地处理稀疏或低分辨率数据
- 缺点:依赖较复杂的数据结构(球体之间的邻接),运行较慢
Reach for the Arcs(RFTA)
核心思想:扩展 RFTS 方法,用弧(而不是直线)来连接球体之间的连接点,从而进一步提升拟合精度,特别是在曲面上。
优点:重建结果更加平滑,精度更高,能更自然地表达曲面变化
缺点:计算更复杂,需要处理圆弧几何
Power Diagram Method
核心思想:一种基于加权点集的空间划分方法,Power Diagram 是 Voronoi 图的推广。每个点有一个“权重”,影响它的作用区域。
在网格重建中的应用:可用于构建 implicit surface,特别是 Poisson reconstruction 的空间划分。在 Dual Contouring 的拓展中也有应用,用于构建更稳定的 dual 网格结构。
优点:可以更好地控制细分区域和权重分布,几何表达能力强
缺点:构建成本较高,数值精度要求高
2025年7月6日 符号距离场及三维重构
隐式曲面 - 符号距离场
有符号距离场基本定义:
定义一个标量场:
$$
f:\mathbb{R}^3\to\mathbb{R}
$$
当值小于零时,该点在表面外,当值小于零时,该点位于表面内,表面即为提取零值面:
$$
{x:f(x)=0}
$$
优点:
- 可以表达任意形状,任意亏格
- 将形状编码为一个函数,可以使用MLP表达
- 方便判断内外、查询距离
- 隐式CSG(Constructive Solid Geometry:构造实体几何)
- 它与曲率有深刻的关联
隐式重建与显式曲面重建的对比:
隐式曲面重建:保流形和光滑形
显式曲面重建:保特征
2025年7月7日 无监督深度学习的四边形网格重建
背景
无监督四边形网格重建主要目的是从点云、网格、深度图、或隐式场等输入中,直接输出结构良好的四边形网格(quad mesh),不依赖显式的 ground-truth quad mesh supervision。常使用几何正则、重建误差、边界对齐等自监督损失。
特点
无需标注数据(如 ground-truth quad mesh)
强调几何约束:如对齐、光滑性、四边形一致性、面角平衡等
常与参数化(parameterization)结合
常见方法/流程
- 隐式字段学习(Implicit Field):通过神经网络拟合输入几何的隐式表示(如 SDF),之后重建四边形网格。
- UV parameterization 学习:将输入模型映射为 2D 平面上规则的四边形图案。
- 四边化优化:在无监督损失下,对神经表示或参数化结果进行优化得到良好四边形划分。
代表性工作
NeurCross: A Neural Approach to Computing Cross Fields for Quad Mesh Generation
QuadriFlow: A Scalable and Robust Method for Quadrangulation(不是深度学习,但常用于比较)
Aligning Gradient and Hessian for Neural Signed Distance Function
2025年7月8日 有监督深度学习的三维重建
背景
此类方法依赖训练集提供的 ground-truth 四边形网格,训练神经网络直接回归或预测目标网格。
特点
- 精度高,但依赖标注数据
- 常用于从图像或深度图生成四边形网格
- 任务多样化:如图像到网格、扫描数据拟合、手工建模辅助
常见方法/流程
- 图像 → 四边形网格:输入 RGB 图片,预测结构化的四边形网格(如用于人脸/衣物等)。
- 深度图 → 四边形网格:结合几何先验,学习从深度图恢复高质量 quad mesh。
- Mesh Refinement:以初始 mesh 为基础,学习对其优化为四边结构。
代表性工作
Laplacian2Mesh: Laplacian-Based Mesh Understanding
2025年7月10日 测地线
等距不变性:
同一个模型,不同的姿势,两个定点之间的测地线距离不会发生变化
梯度 : $\nabla f = (\frac{\partial f}{\partial x_1},\frac{\partial f}{\partial x_2},…,\frac{\partial f}{\partial x_n})$
Input : scalar function $f:\mathbb{R}^n\to\mathbb{R}$
Output : vector field : $\nabla f:\mathbb{R}^n \to \mathbb{R}$
散度 : $divV = \frac{\partial V_x}{\partial x}+\frac{\partial V_y}{\partial y}$
Input : vector field : $V:\mathbb{R}^2 \to \mathbb{R}^2$
Output : scalar function : $divV : \mathbb{R}^2 \to \mathbb{R}$
Laplacian : $\nabla f = div\nabla f = \sum^{3}_{i=1}\frac{\partial f}{\partial x^2_i}$
Input : vector field : $f:\mathbb{R}^n \to \mathbb{R}$
Output : scalar field : $\nabla f:\mathbb{R}^n \to \mathbb{R}$
nbala$\nabla$算子反应的并非本身函数的性质,而是定义域本身的性质,即可以反应曲面本身的性质
网格上的函数
顶点上的值赋值 : $f(x_i) = f_i$
三角形内部的线性插值 : $f(x) = f_iB_i(x) + f_jB_j(x) + f_kB_k(x)$
梯度:
$$
分片线性插值的梯度公式 : \nabla f(x) = f_i\nabla B_i(x) + f_j\nabla B_j(x) + f_k\nabla B_k(x)
= \frac{f_i}{2A_T}(x_k-x_j)^\bot + \frac{f_j}{2A_T}(x_i-x_k)^\bot + \frac{f_k}{2A_T}(x_j-x_i)^\bot
$$
最陡上升方向 $\nabla B_i(x) = \nabla B_i = \frac{(x_k - x_j)^\bot}{2A_T}$
向量场中的散度
一个向量场在三角形内部是分片连续的;
$$
散度定理 : \int_U divV = \int_{\partial U}V.n
$$
即:一个区域内的散度积分等于其边界上的通量。
$$
离散散度表达式:div(V)iA(i) = \sum{ijk}V_{ijk}(xj-xk)^\bot
$$
顶点面积 : $A(i) = \frac{1}{3}\sum_{i\in T}A_T$
即:顶点 $i$ 的面积等于其关联三角形面积的 $\frac{1}{3}$ 加权和。
网格上的拉普拉斯算子
$$
梯度在三角形 $\triangle(x_i, x_j, x_k)$ 内的表达式:(\nabla f){ijk} = \frac{f_i}{2A{ijk}}(x_k-x_j)^\bot + \frac{f_j}{2A_{ijk}}(x_i-x_k)^\bot + \frac{f_k}{2A_{ijk}}(x_j-x_i)^\bot
$$
是每个顶点函数值与对边法向量的线性组合。
$$
拉普拉斯离散形式:(Lf)iA(i) = \sum{ijk}(\nabla f){ijk}.(x_j-x_k)^\bot = \sum{ij}\frac{1}{2}(cot\alpha_{ij}+cos\beta_{ij})(f_i-f_j)
$$
其中 $\alpha_{ij}, \beta_{ij}$ 是边 $(i, j)$ 对应的两个角。
**性质: 如果 $f$ 是常函数,则: : $Lf = 0$ 。**即常函数的拉普拉斯为零。
拉普拉斯矩阵 $L$ 的大小为 $n \times n$,其中 $n$ 是顶点个数。
$$
矩阵系数定义:L_{ij}A(j) = \frac{1}{2}cot(\alpha) + \frac{1}{2}cot(\beta)
$$
矩阵形式(带质量矩阵 $A$): : $AL = -W$
$$
其中 W 是权重矩阵,定义为:W_{ij} =
\left{
\begin{aligned}
\frac{1}{2}(cot(\alpha)+cot{\beta}),if:i ~ j\
-\sum_j W_{ij}, if:i=j\
0, otherwise
\end{aligned}
\right.
$$
$$
质量矩阵 A(Mass Matrix):A_{ij} =
\left{
\begin{aligned}
A(j),if:i = j\
0,otherwise
\end{aligned}
\right.
$$
曲面上的热传导方程
给定一个紧致曲面(compact surface),热传导方程为 : $\frac{\partial f}{\partial t} = \nabla f$
时间离散化:$\frac{f_{t+1}-f_t}{dt} = \nabla f_{t+1}$
空间离散化 : $\frac{f_{t+1}-f_t}{dt} = -A^{-1}Wf_{t+1}$
重排得到的线性系统(求解 $f_{t+1}$):$(A+dtW)f_{t+1} = Af_t$
$$
热核定义:k_t(x,y):\mathbb{R}^+\times M \times M \to \mathbb{R}
$$
它表示在时间$t$内,从点$x$传递到点$y$的热量。
$$
热扩散公式:f(x,t) =\int_M k_t(x,y)f(y,0)dy
$$
表示初始热分布$f(y,0)$在时间$t$后在点$x$的热量。
$$
谱展开形式:k_t(x,y) = \sum_iexp(-t\lambda_i)\phi_i(x)\phi_i(y)
$$
其中:
- $\lambda_i,\phi_i$ 表示拉普拉斯算子的特征值和特征函数;
- 在网格上可用离散拉普拉斯算子的本征对进行数值计算。
离散热核
$$
在网格上,热核可以表示为一个矩阵:k_t = \sum_i exp(-t\lambda_i)\phi_i\phi_i^\bot
$$
其中:
- $\phi_i$是拉普拉斯矩阵的本征向量(长度为顶点数的列向量)
- $k_t$是一个$n\times n$的对称矩阵($n$为顶点数)
- $k_t(x,y)$表示从$x$到$y$的热传递量
离散热扩散公式
$$
给定初始热分布f_0,经过时间t后热量分布为:f_t = \sum_i exp(-t\lambda_i)\phi_i\phi_i^\bot Af_0
$$
$$
或用谱展开记忆形式表示:f_0 = \sum_i\phi_i(\phi_i^\bot Af_0)
$$
其中$A$是质量矩阵(常为对角矩阵,表示每个顶点的面积)。
热核签名
$$
定义:HKS(x) = k_t(x,x) = \sum_i exp(-t\lambda_i)\phi_i(x)^2
$$
物理意义:
表示在时间$t$后**仍保留在点$x$**的热量。
性质:
- 对不同时间梯度$t$的HKS,可以反应局部到整体的几何特征;
- 常用于形状分析、特征点检测、形状匹配等任务。
波核签名
用于衡量某个点在不同频率能量下的响应程度,可以看作是量子力学粒子在形状上驻留的概率分布。
$$
对每个点x和能量水平e,定义为:WKS(x,e) = \sum_{i=0}^{N}exp(-\frac{(e-log\lambda_i)^2}{2\delta^2})\phi_i(x)^2
$$
其中:
- $\lambda_i$:离散拉普拉斯算子的第$i$个特征值;
- $\phi_i(x)$:第$i$个特征函数在点$x$的取值;
- $e$:频率(能量)采样点,通常在$log\lambda$空间中等间距选取;
- $\delta$:带宽控制参数,决定每个频率的范围;
- $N$:使用的特征值/特征函数数量
2025年7月11日 空间划分结构
KD-Tree
基本概念
KD-Tree 是一种二叉树结构,用于在 k 维空间中对点集进行递归划分。每个节点表示一个超平面划分,该超平面与某一维的坐标轴对齐。
构建方式
- 给定一组 k 维点。
- 初始从根节点开始,选择一个维度(如 x 轴)作为划分维度。
- 找到该维度的中位数作为划分点,构建平面将空间分为左右两个子空间。
- 对两个子空间递归进行相同操作,每层轮换划分维度。
应用场景
- 点云搜索(最近邻/范围查询)
- 光线追踪(早期)
- 机器学习(KNN 分类器)
- 地图构建、碰撞检测
特点
- 对静态点集效果良好
- 不适合频繁插入和删除
- 适合低维数据(2D~10D)
Octree(八叉树)
基本概念
Octree 是一种递归八叉划分结构,用于在 3D 空间中对场景/体素/点云进行管理。每个节点将空间分为 8 个等体积的子空间。
构建方式
- 从整个空间开始作为根节点。
- 若当前节点中包含的点/物体数量大于阈值:
- 则将该节点划分为 8 个子立方体,并递归构建。
- 若子块为空则可不存储,形成稀疏结构。
应用场景
- 3D 游戏碰撞检测
- 点云压缩与表示(如 PCL)
- 体绘制(volume rendering)
- 地图建模(SLAM)
特点
- 结构紧凑,适合稀疏3D数据
- 动态更新比 KD-Tree 更方便
- 空间局部性强,适合体素类操作
BSP(Binary Space Partitioning)
基本概念
BSP 是一种基于任意平面划分的二叉空间结构,最早用于2D/3D场景中快速可见性计算与绘制顺序排序。
构建方式
- 选择一个物体面片作为划分平面。
- 用该平面将场景划分为前后两部分:
- 在该面前的物体放入“前子树”
- 在该面后的物体放入“后子树”
- 相交的要进行裁剪或特殊处理
- 递归对每个子空间执行相同划分。
应用场景
- 经典 FPS 游戏(如《DOOM》)
- 可见性计算(从某一点看有哪些物体)
- 渲染排序(Painter’s algorithm)
特点
- 可以使用任意方向平面(比 KD-Tree 更灵活)
- 适合静态场景;动态场景构建代价高
- 可用于处理非轴对齐几何体(如不规则墙面)
BVH(Bounding Volume Hierarchy)
基本概念
BVH 是一种用于快速相交检测的层次包围体结构,常用于光线追踪、碰撞检测等。每个节点代表一个包围体(如 AABB、OBB、球体等),其子节点代表更小的子物体或子包围体。
构建方式
- 对所有物体构建包围盒(如 AABB)。
- 将它们划分为两个子集合,使得两个集合的包围盒重叠最小(如用中轴或 SAH 面积启发式)。
- 递归构建左右子树,每个节点保存当前包围体信息。
应用场景
- 光线追踪(ray tracing)
- 碰撞检测
- GPU 渲染加速
特点
- 动态更新成本比 KD-Tree 小
- 对复杂物体结构更友好
- 使用启发式可提高构建质量(如 SAH)
扩展文章 : Curve Complexity Heuristic KD-trees for Neighborhood-based Exploration of 3D Curves
2025年7月19日 优化
核心问题:我们通常需要解决一个无约束优化问题:
$minimize\ F(x)$
其中$x\in R^n$是我们要优化的目标向量(如顶点位置、相机参数、光照系数等),$F(x) : R^n -> R$ 是我们想要最小化的目标函数(如变形能量、渲染误差、物理势能等)。
牛顿法(Newton’s Method)
- 核心思想: 利用目标函数 $F(x)$ 在当前点 $x_k$ 处的局部二次泰勒展开来近似该函数,然后直接找到这个二次近似函数的最小值点作为下一个迭代点 $x_{k+1}$。它需要用到目标函数的一阶导数(梯度 $g_k = \nabla F(x_k)$)和二阶导数(Hessian矩阵 $H_k = \nabla ^2F(x_k)$)。
- 推导 (直观理解):
- 泰勒展开: 在点 $x_k$ 附近,$F(x)$ 近似为:
$F(x_k + d) ≈ F(x_k) + g_k^T * d + (1/2) * d^T * H_k * d$
其中d
是搜索方向(从 $x_k$ 出发的位移向量)。 - 最小化二次模型: 为了找到使这个二次近似函数最小的 $d$,我们对其关于 $d$ 求导并令导数为零:
$\nabla _d [ … ] = g_k + H_k * d = 0$ - 牛顿方程: 得到线性方程组:
$H_k * d = -g_k$ - 迭代更新: 解这个线性方程组得到搜索方向 $d_k$,然后更新参数:
$x_{k+1} = x_k + d_k$
- 泰勒展开: 在点 $x_k$ 附近,$F(x)$ 近似为:
BFGS (Broyden–Fletcher–Goldfarb–Shanno)
核心思想: BFGS 是最著名、最成功的拟牛顿法 (Quasi-Newton Method) 之一。它不需要显式计算 Hessian 矩阵 $H_k$。取而代之的是,它通过利用当前梯度和上一步的梯度信息,构造一个 Hessian 矩阵的逆 $B_k$(或其近似 $H_k^{-1}$)的近似矩阵。BFGS 直接维护并更新对 $H_k^{-1}$ 的近似 $B_k$。
关键特性:
避免显式 Hessian: 最大的优势是无需计算昂贵的 Hessian,只需计算目标函数的梯度 $g_k$。
近似二阶信息: 通过分析连续迭代点处的梯度和位移变化 $(s_k = x_{k+1} - x_k, y_k = g_{k+1} - g_k)$,BFGS 巧妙地更新 $B_k$ 以满足割线条件 $B_{k+1} * y_k = s_k$。这个条件要求近似的 Hessian 逆在方向 $s_k$ 上的作用效果应与真实的 Hessian 逆一致(至少能正确预测梯度变化 $y_k$)。
收敛速度: 虽然不如牛顿法快,但在适当的条件下(如 Wolfe 线搜索)通常具有超线性收敛速度(介于线性收敛和二次收敛之间),比仅用一阶梯度的方法(如梯度下降)快得多。
保持正定性: BFGS 更新公式设计得当初始 $B_0$ 正定且满足曲率条件 $s_k^T y_k > 0$(通常由 Wolfe 线搜索保证)时,可以保证 $B_k$ 始终保持正定。这确保了搜索方向 $d_k = -B_k * g_k$ 总是下降方向。
存储要求: 需要存储一个稠密的 $n \times n$ 矩阵 $B_k$。这对于大规模问题($n$ 非常大)可能成为瓶颈($O(n²)$ 存储)。针对此问题,有 L-BFGS (Limited-memory BFGS) 变种。
L-BFGS:
解决存储问题: L-BFGS 是 BFGS 为处理大规模优化问题而设计的变体。它不存储完整的 $n \times n$ 近似矩阵 $B_k$。
工作原理: 它只存储最近 $m$(通常 $m$ 很小,如 $5-20$)步的位移向量 $s_k$ 和梯度变化向量 $y_k$。利用这些向量,L-BFGS 在需要计算搜索方向 $d_k = -B_k * g_k$ 时,通过一个巧妙的递归公式,仅使用 $g_k$ 和存储的 ${s_i, y_i}$ 序列$(i = k-m, …, k-1)$来隐式地计算出 $B_k * g_k$ 的结果(即 $-d_k$),而无需显式构造 $B_k$。
优势: 存储需求从 $O(n²)$ 显著降低到 $O(m*n)$,使其能够高效处理参数维度 $n$ 高达数百万甚至更大的问题。收敛速度通常接近完整的 BFGS。
梯度下降法 (Gradient Descent) 及其变种:
- 基本思想: 沿着当前点负梯度方向 (
d_k = -g_k
) 进行搜索,找到使函数值下降的点。是最简单的一阶方法。 - 变种:
- 最速下降法 (Steepest Descent): 一种特定的梯度下降,但在图形学中术语常混用。
- 动量法 (Momentum): 在更新方向中加入上一步更新的惯性,帮助加速收敛并减少震荡(如穿越狭窄山谷)。
- Nesterov 加速梯度 (NAG): Momentum 的改进版,提供更好的理论收敛性质。
- AdaGrad/RMSProp/Adam: 自适应学习率算法。Adam (Adaptive Moment Estimation) 是目前极其流行且鲁棒的一阶优化器,它结合了动量(一阶矩估计)和自适应学习率(二阶矩估计),对超参数(尤其是学习率)不太敏感,在训练深度学习模型中几乎成为标配,在图形学中涉及深度学习的任务(如神经渲染、生成模型)也广泛应用。
2025年7月20日 分片光滑结构的几何表示
核心问题:表示具有不连续特征(如折痕、边界)的连续曲面,常见于CAD建模和几何处理。
核心思想:
将复杂曲面分解为多个光滑曲面片(patches),在相邻面片连接处施加连续性约束($C^0$, $C^1$, $G^1$ 等),同时允许特定位置存在不连续性。关键方法:
样条表示:NURBS/T-Splines 通过控制点和节点向量定义光滑曲面片,边界处通过节点重复实现连续性控制
细分曲面:Catmull-Clark/Loop 细分规则在极限曲面产生 $C^1$/ $C^2$ 连续,通过特殊规则处理特征边(如尖锐折痕)
基于网格的方法:
显式标记特征边(crease edges)
在非特征区域使用双拉普拉斯平滑
特征边界处采用局部参数化重组
混合表示:结合隐式函数(RBF)和显式网格处理复杂拓扑
2025年7月21日 三维点云的法向一致性相关
核心问题:为无结构点云估计一致朝向的法向量,避免重建曲面时出现孔洞或自交。
- 核心思想:利用局部几何结构和全局传播机制,使相邻点法向共轭(即指向曲面同侧)。
- 关键技术:
- 局部估计:
- PCA 法:对 $k$-NN 邻域协方差矩阵最小特征向量
- 加权最小二乘平面拟合
- 全局一致化:
- 最小生成树(MST)传播:从种子点开始沿最近邻图传播方向
- 基于视线约束:利用扫描视角信息($\mathbf{n} \cdot (\mathbf{c}-\mathbf{p}) > 0$)
- 图割优化:构建能量函数 $E=\sum_{(i,j)} \mathbf{n}_i \cdot \mathbf{n}_j - \lambda \mathbf{n}_i \cdot (\mathbf{p}_j-\mathbf{p}_i)$
- 深度学习方法:
- PCPNet 等网络直接预测一致法向
- 通过法向-位置联合损失函数增强一致性
- 局部估计:
2025年7月22日 基元检测
核心问题:从点云/网格中自动检测基本几何形状(平面、圆柱、球体等)。
- 核心思想:将复杂几何体分解为简单几何基元(Primitives)的组合。
- 主流方法:
- 传统方法:
- RANSAC:随机采样拟合基元,通过内点数量验证假设
- Hough 变换:将点映射到参数空间累积投票
- 区域生长:基于法向/曲率相似性聚类
- 深度学习方法:
- SPFN:端到端预测基元类型和参数
- 基于图神经网络的分割+拟合
- 混合方法:
- 先通过深度学习粗分割,再用最小二乘精确拟合
- 基元间关系建模(如正交性约束)
- 传统方法:
2025年7月23日 AIGC基本原理
核心问题:利用AI生成符合人类需求的视觉/几何内容。
核心思想:学习数据分布并采样生成新样本,实现”从描述到内容”的转化。
关键组件:
- 文本编码器(如CLIP)
- 去噪网络(U-Net架构)
- 调节机制(Classifier-free Guidance)
2025年7月24日 Offset
核心问题:构建与原始几何体保持恒定距离的新曲面。
数学定义:
Soffset={p±d⋅n(p)∣p∈S}Soffset={p±d⋅n(p)∣p∈S}
其中 $d$ 为偏移距离,$\mathbf{n}$ 为单位法向。
技术挑战:
- 自交处理:
- 距离场裁剪($d < 1/\kappa_{max}$)
- 拓扑修复(MAT 引导)
- 特征保持:
- 尖角处圆弧过渡
- 曲率自适应偏移
- 高效计算:
- GPU 并行距离场生成
- 层次化 AABB 树检测碰撞
- 自交处理:
2025年7月25日 中轴
核心问题:提取形状的拓扑骨架和尺寸信息。
核心定义:最大内切球的圆心集合,满足:
MA(Ω)={x∈Ω∣∃p1,p2∈∂Ω,∥x−p1∥=∥x−p2∥=rmax(x)}M**A(Ω)={x∈Ω∣∃p1,p2∈∂Ω,∥x−p1∥=∥x−p2∥=rmax(x)}
计算方法:
方法 原理 优点 缺点 Voronoi法 计算边界点Voronoi图取内部边 理论完备 噪声敏感 距离场法 提取距离场脊线 抗噪性好 计算昂贵 收缩法 几何驱动收缩 保留特征 需迭代优化 应用场景:
- 网格简化(QEM 基于中轴)
- 动画骨骼生成
- 增材制造支撑结构优化
2025年7月26日 AIGC更多应用
核心领域:计算机图形学中的创新应用
- 3D内容生成:
- 文本→3D:DreamFusion(SDS损失)、Point-E
- 图像→3D:PIFuHD(隐式函数)
- 生成式CAD:AutoCAD SketchGraph
- 材质与光照:
- 神经辐射场(NeRF)材质解耦
- 基于物理的材质生成(DiffMat)
- 动画合成:
- 运动风格迁移(VAE+GAN)
- 面部表情生成(3DMM+Diffusion)
- 场景生成:
- ProcTHOR:程序化室内场景
- Gaia:开放世界地形生成
2025年7月26日 3DGS的基本原理
核心问题:实现实时的神经辐射场渲染。
- 关键技术:
- 椭球投影:
Σ′=JWΣWTJTΣ′=J**WΣWTJ**T
其中 $J$ 为投影雅可比,$W$ 为视角矩阵 - 自适应控制:
- 梯度监控:$|\nabla \mathcal{L}|$ 过大时分裂高斯
- 尺度监控:$\max(\sigma) > \theta$ 时克隆高斯
- 椭球投影:
2025年7月27日 3DGS
优化与扩展:提升3DGS的实用性和表现力
训练加速技术:
层次化初始化:从SfM点云构建初始高斯
损失函数:
L=(1−λ)∥I^−I∥1+λD-SSIM(I^,I)L=(1−λ)∥I^−I∥1+λD-SSIM(I^,I)
CUDA优化:并行排序(Radix Sort on GPU)
动态场景处理:
- 4D高斯:$ \mu(t) = \mu_0 + \mathbf{v}t $
- 形变场:MLP预测位移 $\delta \mu = f(\mu, t)$
语义增强:
- 嵌入语义高斯:$\mathbf{s} \in \mathbb{R}^k$ 附加特征向量
- 应用:交互式编辑、物体分割
局限与突破:
问题 解决方案 显存消耗 高斯剪枝($\alpha < \tau$) 透明物体 折射建模(Snell’s Law) 镜面反射 微表面高斯扩展
每个主题均保持技术深度和结构一致性,符合您要求的格式标准。